url = 'https://www.acwing.com/problem/content/852/'

from queue import PriorityQueue
import sys

N = 1000010

h = [-1] * N
e = [0] * N
ne = [0] * N
w = [0] * N
idx = 0
dist = [sys.maxsize] * N
st = [False] * N

def add(a, b, c):
    global idx
    e[idx], w[idx], ne[idx], h[a] = b, c, h[a], idx
    idx += 1

def dijkstra():
    global dist
    global st
    dist[1] = 0
    heap = PriorityQueue()
    heap.put((0, 1))

    while not heap.empty():
        distance, ver = heap.get()

        if st[ver]:
            continue
        st[ver] = True

        i = h[ver]
        while i != -1:
            j = e[i]
            if dist[j] > dist[ver] + w[i]:
                dist[j] = dist[ver] + w[i]
                heap.put((dist[j], j))
            i = ne[i]

    if dist[n] == sys.maxsize:
        return -1
    return dist[n]

n, m = map(int, input().split())

for i in range(m):
    a, b, c = map(int, input().split())
    add(a, b, c)

print(dijkstra())
